<?xml version="1.0" encoding="utf-8" ?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<meta name="generator" content="Docutils 0.4: http://docutils.sourceforge.net/" />
<title>Permanent Data Storage (Flash)</title>
<meta name="author" content="David Gay, Jonathan Hui" />
<style type="text/css">

/*
:Author: David Goodger
:Contact: goodger@users.sourceforge.net
:date: $Date: 2009-02-03 23:07:32 $
:version: $Revision: 1.9 $
:copyright: This stylesheet has been placed in the public domain.

Default cascading style sheet for the HTML output of Docutils.
*/
body {
  font-family: Times;
  font-size: 16px;
}

.first {
  margin-top: 0 ! important }

.last {
  margin-bottom: 0 ! important }

.hidden {
  display: none }

a.toc-backref {
  text-decoration: none ;
  color: black }

blockquote.epigraph {
  margin: 2em 5em ; }

dd {
  margin-bottom: 0.5em }

div.abstract {
  margin: 2em 5em }

div.abstract p.topic-title {
  font-weight: bold ;
  text-align: center }

div.attention, div.caution, div.danger, div.error, div.hint,
div.important, div.note, div.tip, div.warning, div.admonition {
  margin: 2em ;
  border: medium outset ;
  padding: 1em }

div.attention p.admonition-title, div.caution p.admonition-title,
div.danger p.admonition-title, div.error p.admonition-title,
div.warning p.admonition-title {
  color: red ;
  font-weight: bold ;
  font-family: sans-serif }

div.hint p.admonition-title, div.important p.admonition-title,
div.note p.admonition-title, div.tip p.admonition-title,
div.admonition p.admonition-title {
  font-weight: bold ;
  font-family: sans-serif }

div.dedication {
  margin: 2em 5em ;
  text-align: center ;
  font-style: italic }

div.dedication p.topic-title {
  font-weight: bold ;
  font-style: normal }

div.figure {
  margin-left: 2em }

div.footer, div.header {
  font-size: smaller }

div.line-block {
  display: block ;
  margin-top: 1em ;
  margin-bottom: 1em }

div.line-block div.line-block {
  margin-top: 0 ;
  margin-bottom: 0 ;
  margin-left: 1.5em }

div.sidebar {
  margin-left: 1em ;
  border: medium outset ;
  padding: 0em 1em ;
  background-color: #ffffee ;
  width: 40% ;
  float: right ;
  clear: right }

div.sidebar p.rubric {
  font-family: sans-serif ;
  font-size: medium }

div.system-messages {
  margin: 5em }

div.system-messages h1 {
  color: red }

div.system-message {
  border: medium outset ;
  padding: 1em }

div.system-message p.system-message-title {
  color: red ;
  font-weight: bold }

div.topic {
  margin: 2em }

h1 {
  font-family: Arial, sans-serif;
  font-size: 20px;
}

h1.title {
 text-align: center;
 font-size: 32px;
}

h2 {
 font-size: 16px;
 font-family: Arial, sans-serif;
}

h2.subtitle {
  text-align: center }

h3 {
 font-size: 12px;
 font-family: Arial, sans-serif;
}

hr {
  width: 75% }

ol.simple, ul.simple {
  margin-bottom: 1em }

ol.arabic {
  list-style: decimal }

ol.loweralpha {
  list-style: lower-alpha }

ol.upperalpha {
  list-style: upper-alpha }

ol.lowerroman {
  list-style: lower-roman }

ol.upperroman {
  list-style: upper-roman }

p.attribution {
  text-align: right ;
  margin-left: 50% }

p.caption {
  font-style: italic }

p.credits {
  font-style: italic ;
  font-size: smaller }

p.label {
  white-space: nowrap }

p.rubric {
  font-weight: bold ;
  font-size: larger ;
  color: maroon ;
  text-align: center }

p.sidebar-title {
  font-family: sans-serif ;
  font-weight: bold ;
  font-size: larger }

p.sidebar-subtitle {
  font-family: sans-serif ;
  font-weight: bold }

p.topic-title {
  font-weight: bold }

pre.address {
  margin-bottom: 0 ;
  margin-top: 0 ;
  font-family: serif ;
  font-size: 100% }

pre.line-block {
  font-family: serif ;
  font-size: 100% }

pre.literal-block, pre.doctest-block {
  margin-left: 2em ;
  margin-right: 2em ;
  background-color: #eeeeee;
  border-color: #000000;
  border-width: thin; 
  font-size: 14px
}

span.classifier {
  font-family: sans-serif ;
  font-style: oblique }

span.classifier-delimiter {
  font-family: sans-serif ;
  font-weight: bold }

span.interpreted {
  font-family: sans-serif }

span.option {
  white-space: nowrap }

span.option-argument {
  font-style: italic }

span.pre {
  white-space: pre }

span.problematic {
  color: red }

table {
  margin-top: 0.5em ;
  margin-bottom: 0.5em }

table.citation {
  border-left: solid thin gray ;
  padding-left: 0.5ex }

table.docinfo {
  margin: 2em 4em;
}

table.footnote {
  border-left: solid thin black ;
  padding-left: 0.5ex }

td, th {
  padding-left: 0.5em ;
  padding-right: 0.5em ;
  vertical-align: top }

th.docinfo-name, th.field-name {
  font-weight: bold ;
  text-align: left ;
  white-space: nowrap;
  }

h1 tt, h2 tt, h3 tt, h4 tt, h5 tt, h6 tt {
  font-size: 100% }

tt {}

ul.auto-toc {
  list-style-type: none }

</style>
</head>
<body>
<div class="document" id="permanent-data-storage-flash">
<h1 class="title">Permanent Data Storage (Flash)</h1>
<table class="docinfo" frame="void" rules="none">
<col class="docinfo-name" />
<col class="docinfo-content" />
<tbody valign="top">
<tr class="field"><th class="docinfo-name">TEP:</th><td class="field-body">103</td>
</tr>
<tr class="field"><th class="docinfo-name">Group:</th><td class="field-body">Core Working Group</td>
</tr>
<tr class="field"><th class="docinfo-name">Type:</th><td class="field-body">Documentary</td>
</tr>
<tr><th class="docinfo-name">Status:</th>
<td>Final</td></tr>
<tr class="field"><th class="docinfo-name">TinyOS-Version:</th><td class="field-body">2.x</td>
</tr>
<tr><th class="docinfo-name">Author:</th>
<td>David Gay, Jonathan Hui</td></tr>
</tbody>
</table>
<div class="note">
<p class="first admonition-title">Note</p>
<p class="last">This memo documents a part of TinyOS for the TinyOS Community, and
requests discussion and suggestions for improvements.  Distribution
of this memo is unlimited. This memo is in full compliance with
TEP 1.</p>
</div>
<div class="section">
<h1><a id="abstract" name="abstract">Abstract</a></h1>
<p>This memo documents a set of hardware-independent interfaces to non-volatile
storage for TinyOS 2.x. It describes some design principles for the HPL and
HAL layers of various flash chips.</p>
</div>
<div class="section">
<h1><a id="introduction" name="introduction">1. Introduction</a></h1>
<p>Flash chips are a form of EEPROM (electrically-erasable, programmable
read-only memory), distinguished by a fast erase capability. However,
erases can only be done in large units (from 256B to 128kB depending on the
flash chip). Erases are the only way to switch bits from 0 to 1, and
programming operations can only switch 1's to 0's. Additionally, some
chips require that programming only happen once between each erase,
or that it be in relatively large units (e.g., 256B).</p>
<p>In the table below, we summarise these differences by categorising
flash chips by their underlying technology (NOR vs NAND). We also
include a column for Atmel's AT45DB flash chip family, as it has
significantly different tradeoffs than other flash chips:</p>
<blockquote>
<table border="1" class="docutils">
<colgroup>
<col width="19%" />
<col width="27%" />
<col width="25%" />
<col width="28%" />
</colgroup>
<thead valign="bottom">
<tr><th class="head">X</th>
<th class="head">NOR
(ex: ST M25P40,
Intel PXA27x)</th>
<th class="head">AT45DB</th>
<th class="head">NAND
(ex: Samsung
K9K1G08R0B)</th>
</tr>
</thead>
<tbody valign="top">
<tr><td>Erase</td>
<td>Slow (seconds)</td>
<td>Fast (ms)</td>
<td>Fast (ms)</td>
</tr>
<tr><td>Erase unit</td>
<td>Large (64KB-128KB)</td>
<td>Small (256B)</td>
<td>Medium (8KB-32KB)</td>
</tr>
<tr><td>Writes</td>
<td>Slow (100s kB/s)</td>
<td>Slow (60kB/s)</td>
<td>Fast (MBs/s)</td>
</tr>
<tr><td>Write unit</td>
<td>1 bit</td>
<td>256B</td>
<td>100's of bytes</td>
</tr>
<tr><td>Bit-errors</td>
<td>Low</td>
<td>Low</td>
<td>High (requires ECC,
bad-block mapping)</td>
</tr>
<tr><td>Read</td>
<td>Bus limited <a class="footnote-reference" href="#id3" id="id1" name="id1">[*]</a></td>
<td>Slow+Bus limited</td>
<td>Bus limited</td>
</tr>
<tr><td>Erase cycles</td>
<td>10^4 - 10^5</td>
<td>10^4 <a class="footnote-reference" href="#id4" id="id2" name="id2">[†]</a></td>
<td>10^5 - 10^7</td>
</tr>
<tr><td>Intended use</td>
<td>Code storage</td>
<td>Data storage</td>
<td>Data storage</td>
</tr>
<tr><td>Energy/byte</td>
<td>1uJ</td>
<td>1uJ</td>
<td>.01uJ</td>
</tr>
</tbody>
</table>
</blockquote>
<table class="docutils footnote" frame="void" id="id3" rules="none">
<colgroup><col class="label" /><col /></colgroup>
<tbody valign="top">
<tr><td class="label"><a class="fn-backref" href="#id1" name="id3">[*]</a></td><td>M25P40 reads are limited by the use of a 25MHz SPI bus. The PXA27x flash
is memory mapped (reads are very fast and can directly execute code).</td></tr>
</tbody>
</table>
<table class="docutils footnote" frame="void" id="id4" rules="none">
<colgroup><col class="label" /><col /></colgroup>
<tbody valign="top">
<tr><td class="label"><a class="fn-backref" href="#id2" name="id4">[†]</a></td><td>Or infinite? Data sheet just says that every page within a sector
must be written every 10^4 writes within that sector</td></tr>
</tbody>
</table>
<p>The energy/byte is the per-byte cost of erasing plus programming. It is
derived from the timing and power consumption of erase and write operations
(for NOR flash, values are for the STMicroelectronics M25P family, for NAND
flash, values are from the Samsung datasheet). Energy/byte for reads appears
to depend mostly on how long the read takes (the power consumptions are
comparable), i.e., on the efficiency of the bus + processor.</p>
<p>Early TinyOS platforms all used a flash chip from the AT45DB
family. In TinyOS 1.x, this chip could be accessed through three
different components:</p>
<ul class="simple">
<li>Using a low-level interface (<tt class="docutils literal"><span class="pre">PageEEPROMC</span></tt>) which gave direct
access to per-page read, write and erase operations.</li>
<li>Using a high-level memory-like interface (<tt class="docutils literal"><span class="pre">ByteEEPROMC</span></tt>) with
read, write and logging operations.</li>
<li>Using a simple file system (<tt class="docutils literal"><span class="pre">Matchbox</span></tt>) with sequential-only
files [<a class="reference" href="#id5">1</a>].</li>
</ul>
<p>Some more recent platforms use different flash chips: the ST M25P family (Telos
rev. B, eyes) and the Intel Strataflash (Intel Mote2). None of the
three components listed above are supported on these chips:</p>
<ul class="simple">
<li>The <tt class="docutils literal"><span class="pre">PageEEPROMC</span></tt> component is (and was intended to be) AT45DB-specific</li>
<li><tt class="docutils literal"><span class="pre">ByteEEPROMC</span></tt> allows arbitrary rewrites of sections of the flash.
This is not readily implementable on a flash chip with large erase units.</li>
<li>The <tt class="docutils literal"><span class="pre">Matchbox</span></tt> implementation was AT45DB-specific. It was not
reimplemented for these other chips, in part because it does not
support some applications (e.g., network reprogramming) very well.</li>
</ul>
</div>
<div class="section">
<h1><a id="storage-in-tinyos-2-x" name="storage-in-tinyos-2-x">2. Storage in TinyOS 2.x</a></h1>
<p>One approach to hiding the differences between different flash chips is to
provide a disk-like, block interface (with, e.g., 512B blocks). This is the
approach taken by compact flash cards. However, in the context of TinyOS,
this approach has several drawbacks:</p>
<ul class="simple">
<li>This approach is protected by patents, making it difficult to provide
in a free, open-source operating system.</li>
<li>To support arbitrary block writes where blocks are smaller than the
erase unit, and to deal with the limited number of erase cycles/block
requires remapping blocks. We believe that maintaining this remapping
table is too expensive on many mote-class devices.</li>
</ul>
<p>A second approach is to provide a generic low-level interface providing
operations (read, write, erase) corresponding to the basic flash
operations, along with information describing the flash chip's layout
(minimum write and erase unit, timing information, etc). However,
we believe that the large differences between NAND and NOR flash (see the
table above), in particular the differences in reliability, write and
erase units, make the design of a useful generic low-level interface
tricky at best.</p>
<p>We thus believe it is best, for now at least, to define high-level
storage abstractions that are useful for sensor network applications,
and leave their implementation up to each flash chip - such abstractions
will be necessary anyway. We leave open the possibility that a future
TEP may define portable lower-level flash interfaces (either for all
flash chips, or, e.g., for NOR-family flashes). Such low-level
interfaces would allow implementations of the storage abstractions
defined in this TEP to be used for multiple flash chips.</p>
<p>This TEP describes three high-level storage abstractions: large objects
written in a single session, small objects with arbitrary reads and
writes, and logs. TinyOS 2.x, divides flash chips into separate volumes
(with sizes fixed at compile-time). Each volume provides a single
storage abstraction (the abstraction defines the format).</p>
<p>We prefer the use of single abstractions over fixed-size volumes over
the use of a more general filing system (like Matchbox) for several
reasons:</p>
<ul class="simple">
<li>TinyOS is currently targeted at running a single application, and many
applications know their storage needs in advance: for instance, a
little space for configuration data, and everything else for a log of
all sampled data. In such cases, the flexibility offered by a filing
system (e.g., arbitrary numbers of files) is overkill,</li>
<li>Each abstraction is relatively easy to implement on a new flash chip, and
has relatively little overhead.</li>
<li>The problem of dealing with the limited number of erase cycles/block
is simplified: it is unlikely that user applications will need to
rewrite the same small object 100'000 times, or cycle 100'000 times
through their log. Thus the abstractions can mostly ignore the need for
&quot;wear levelling&quot; (ensuring that each block of the flash is erased
the same number of time, to maximise flash chip lifetime).</li>
</ul>
<p>New abstractions (including a filing system) can easily be added to
this framework.</p>
<p>The rest of this TEP covers some principles for the organisation of
flash chips (Section 3), then describes the flash volumes and
storage abstractions in detail (Section 4).</p>
</div>
<div class="section">
<h1><a id="hpl-hal-hil-architecture" name="hpl-hal-hil-architecture">3. HPL/HAL/HIL Architecture</a></h1>
<p>The flash chip architecture follows the three-layer Hardware
Abstraction Architecture (HAA), with each chip providing a presentation
layer (HPL, Section 3.1), adaptation layer (HAL, Section 3.2) and
platform-independent interface layer (HIL, Section 3.3) [<a class="reference" href="#id6">2</a>].
The implementation of these layers SHOULD be found in the
<tt class="docutils literal"><span class="pre">tos/chips/CHIPNAME</span></tt> directory. If a flash chip is part of a larger
family with a similar interface, the HAA SHOULD support all family members
by relying, e.g., on platform-provided configuration information.</p>
<p>Appendix A shows example HPL and HAL specifications for the AT45DB
and ST M25P chip families.</p>
<div class="section">
<h2><a id="hardware-presentation-layer-hpl" name="hardware-presentation-layer-hpl">3.1 Hardware Presentation Layer (HPL)</a></h2>
<p>The flash HPL has a chip-dependent, platform-independent interface. The
implementation of this HPL is platform-dependent. The flash HPL SHOULD be
stateless.</p>
<p>To remain platform independent, a flash chip's HPL SHOULD connect to
platform-specific components
providing access to the flash chip; these components
SHOULD be placed in the <tt class="docutils literal"><span class="pre">tos/platforms/PLATFORM/chips/CHIPNAME</span></tt>
directory. If the flash chip implementation supports a family of
flash chips, this directory MAY also contain a file describing the
particular flash chip found on the platform.</p>
</div>
<div class="section">
<h2><a id="hardware-adaptation-layer-hal" name="hardware-adaptation-layer-hal">3.2 Hardware Adaptation Layer (HAL)</a></h2>
<p>The flash HAL has a chip-dependent, platform-independent interface and
implementation. Flash families with a common HPL SHOULD have a common
HAL. Flash HAL's SHOULD expose a <tt class="docutils literal"><span class="pre">Resource</span></tt> interface and automatically
power-manage the underlying flash chip. Finally, the flash HAL MUST
provide a way to access the volume information specified by the
programmer (see Section 3). This allows users to build new flash
abstractions that interact cleanly with the rest of the flash system.</p>
</div>
<div class="section">
<h2><a id="hardware-interface-layer-hil" name="hardware-interface-layer-hil">3.3 Hardware Interface Layer (HIL)</a></h2>
<p>Each flash chip MUST support at least one of the storage abstractions
described in Section 4. These abstractions SHOULD be presented in
components named <tt class="docutils literal"><span class="pre">ChipAbstractionC</span></tt>, e.g., <tt class="docutils literal"><span class="pre">At45dbLogStorageC</span></tt>.
Additionally, a flash chip implementation MAY support platforms
with multiple instances of the same storage chip. The way in which
this is achieved is not specified further in this TEP.</p>
<p>Each platform MUST have <tt class="docutils literal"><span class="pre">AbstractionC</span></tt> components (e.g.,
<tt class="docutils literal"><span class="pre">LogStorageC</span></tt>) implementing the storage abstractions of Section 4
supported by its flash chip(s). On platforms with multiple storage chips
SHOULD redirect uses of <tt class="docutils literal"><span class="pre">AbstractionC</span></tt> to the appropriate storage
chip, based on the requested volume.</p>
</div>
</div>
<div class="section">
<h1><a id="non-volatile-storage-abstractions" name="non-volatile-storage-abstractions">4. Non-Volatile Storage Abstractions</a></h1>
<p>The HIL implementations are platform-independent, but chip (family)
dependent. They implement the three storage abstractions and
volume structure discussed in the introduction.</p>
<div class="section">
<h2><a id="volumes" name="volumes">4.1. Volumes</a></h2>
<p>The division of the flash chip into fixed-size volumes is specified by
an XML file that is placed in the application's directory (where one
types 'make'). The XML file specifies the allocation as follows:</p>
<pre class="literal-block">
&lt;volume_table&gt;
  &lt;volume name=&quot;DELUGE0&quot; size=&quot;65536&quot; /&gt;
  &lt;volume name=&quot;CONFIGLOG&quot; size=&quot;65536&quot; /&gt;
  &lt;volume name=&quot;DATALOG&quot; size=&quot;131072&quot; /&gt;
  &lt;volume name=&quot;GOLDENIMAGE&quot; size=&quot;65536&quot; base=&quot;983040&quot; /&gt;
&lt;/volume_table&gt;
</pre>
<p>The name and size parameters are required, while base is optional. The name
is a string containing one or more characters in [a-zA-Z0-9_], while size
and base are in bytes. Each storage chip MUST provide a compile-time tool
that translates the allocation specification to chip-specific nesC
code. There is no constraint on how this is done or what code is produced,
except that the specification to physical allocation MUST be one-to-one
(i.e. a given specification should always have the same resulting physical
allocation on a given chip) and the result MUST be placed in the build
directory. When not specified, the tool picks a suitable physical
location for a volume. If there is any reason that the physical allocation
cannot be satisfied, an error should be given at compile time. The tool
SHOULD be named <tt class="docutils literal"><span class="pre">tos-storage-CHIPNAME</span></tt> and be distributed with the other
tools supporting a platform. The XML file SHOULD be named
<tt class="docutils literal"><span class="pre">volumes-CHIPNAME.xml</span></tt>.</p>
<p>The compile-time tool MUST prepend 'VOLUME_' to each volume name in
the XML file and '#define' each resulting name to map to a unique
integer.</p>
<p>The storage abstractions are accessed by instantiating generic
components that take the volume macro as argument:</p>
<pre class="literal-block">
components new BlockStorageC(VOLUME_DELUGE0);
</pre>
<p>If the named volume is not in the specification, nesC will give a
compile-time error since the symbol will be undefined.</p>
<p>A volume MUST NOT be used with more than one storage abstraction instance.</p>
</div>
<div class="section">
<h2><a id="large-objects" name="large-objects">4.2 Large objects</a></h2>
<p>The motivating example for large objects is the transmission or
long-term storage of large pieces of data. For instance, programs in a
network-reprogramming system, or large data-packets in a reliable
data-transmission system. Such objects have an interesting
characteristic: each byte in the object is written at most once.</p>
<p>This leads to the definition of the <tt class="docutils literal"><span class="pre">BlockStorageC</span></tt> abstraction for storing
large objects or other &quot;write-once&quot; objects:</p>
<ul class="simple">
<li>A large object ranges from a few kilobytes upwards.</li>
<li>A large object is erased before the first write.</li>
<li>A sync ensures that a large object survives a reboot or crash</li>
<li>Reads are unrestricted</li>
<li>Each byte can only be written once between two erases</li>
</ul>
<p>Large objects are accessed by instantiating a BlockStorageC component
which takes a volume id argument:</p>
<pre class="literal-block">
generic configuration BlockStorageC(volume_id_t volid) {
  provides {
      interface BlockWrite;
      interface BlockRead;
  }
} ...
</pre>
<p>The <tt class="docutils literal"><span class="pre">BlockRead</span></tt> and <tt class="docutils literal"><span class="pre">BlockWrite</span></tt> interfaces (briefly presented in
Appendix B) contain the following operations (all split-phase, except
<tt class="docutils literal"><span class="pre">BlockRead.getSize</span></tt>):</p>
<ul class="simple">
<li><tt class="docutils literal"><span class="pre">BlockWrite.erase</span></tt>: erase the volume. After a reboot or a commit, a
volume MUST be erased before it can be written to.</li>
<li><tt class="docutils literal"><span class="pre">BlockWrite.write</span></tt>: write some bytes starting at a given
offset. Each byte MUST NOT be written more than once between two erases.</li>
<li><tt class="docutils literal"><span class="pre">BlockWrite.sync</span></tt>: ensure all previous writes are present on a given
volume. Sync MUST be called to ensure written data survives a reboot
or crash.</li>
<li><tt class="docutils literal"><span class="pre">BlockRead.read</span></tt>: read some bytes starting at a given offset.</li>
<li><tt class="docutils literal"><span class="pre">BlockRead.computeCrc</span></tt>: compute the CRC of some bytes starting at a
given offset.</li>
<li><tt class="docutils literal"><span class="pre">BlockRead.getSize</span></tt>: return bytes available for large object storage in
volume.</li>
</ul>
<p>For full details on arguments and other considerations, see the comments in
the interface definitions.</p>
<p>Note that these interfaces contain no direct support for verifying the
integrity of the BlockStorage data, but such support can easily be built
by using the <tt class="docutils literal"><span class="pre">computeCrc</span></tt> command and storing the result in a
well-defined location, and checking this CRC when desired.</p>
</div>
<div class="section">
<h2><a id="logging" name="logging">4.3 Logging</a></h2>
<p>Event and result logging is a common requirement in sensor
networks. Such logging should be reliable (a mote crash should not
lose data). It should also be easy to extract data from the log,
either partially or fully. Some logs are <em>linear</em> (stop logging when
the volume is full), others are <em>circular</em> (the oldest data is
overwritten when the volume is full).</p>
<p>The <tt class="docutils literal"><span class="pre">LogStorageC</span></tt> abstraction supports these requirements.  The log is
record based: each call to <tt class="docutils literal"><span class="pre">LogWrite.append</span></tt> (see below) creates a new
record. On failure (crash or reboot), the log MUST only lose whole
records from the end of the log. Additionally, once a circular log wraps
around, calls to <tt class="docutils literal"><span class="pre">LogWrite.append</span></tt> MUST only lose whole records from
the beginning of the log.</p>
<p>Logs are accessed by instantiating a LogStorageC component which takes a
volume id and a boolean argument:</p>
<pre class="literal-block">
generic configuration LogStorageC(volume_id_t volid, bool circular) {
  provides {
      interface LogWrite;
      interface LogRead;
  }
} ...
</pre>
<p>If the <tt class="docutils literal"><span class="pre">circular</span></tt> argument is TRUE, the log is circular; otherwise
it is linear.</p>
<p>The <tt class="docutils literal"><span class="pre">LogRead</span></tt> and <tt class="docutils literal"><span class="pre">LogWrite</span></tt> interfaces (briefly presented in
Appendix B) contain the following operations (all split-phase except
<tt class="docutils literal"><span class="pre">LogWrite.currentOffset</span></tt>, <tt class="docutils literal"><span class="pre">LogRead.currentOffset</span></tt> and
<tt class="docutils literal"><span class="pre">LogRead.getSize</span></tt>):</p>
<ul>
<li><p class="first"><tt class="docutils literal"><span class="pre">LogWrite.erase</span></tt>: erase the log. A log MUST be erased (possibly in
some previous session) before any other operation can be used.</p>
</li>
<li><p class="first"><tt class="docutils literal"><span class="pre">LogWrite.append</span></tt>: append some bytes to the log. In a circular log,
this may overwrite the current read position. In this case, the
read position MUST be advanced to the log's current beginning
(i.e., as if <tt class="docutils literal"><span class="pre">LogRead.seek</span></tt> had been called with <tt class="docutils literal"><span class="pre">SEEK_BEGINNING</span></tt>).
Additionally, the <tt class="docutils literal"><span class="pre">LogWrite.appendDone</span></tt> event reports whenever, in a
circular log, an append MAY have erased old records.</p>
<p>Each append creates a separate record. Log implementations may have a
maximum record size; all implementations MUST support records of up
to 255 bytes.</p>
</li>
<li><p class="first"><tt class="docutils literal"><span class="pre">LogWrite.sync</span></tt>: guarantee that data written so far will not be lost to
a crash or reboot (it can still be overwritten when a circular log wraps
around). Using <tt class="docutils literal"><span class="pre">sync</span></tt> MAY waste some space in the log.</p>
</li>
<li><p class="first"><tt class="docutils literal"><span class="pre">LogWrite.currentOffset</span></tt>: return cookie representing current
append position (for use with <tt class="docutils literal"><span class="pre">LogRead.seek</span></tt>).</p>
</li>
<li><p class="first"><tt class="docutils literal"><span class="pre">LogRead.read</span></tt>: read some bytes from the current read position in
the log and advance the read position.</p>
<p><tt class="docutils literal"><span class="pre">LogStorageC</span></tt> implementations MUST include error detection codes
to increase the likelihood of detection of corrupted or invalid log
data. Data returned by a successful read MUST have passed this
error detection check. The behaviour on failure of this check is
unspecified (e.g., the at45db believes as if the end of the log has
been reached; other implementations may behave differently).</p>
</li>
<li><p class="first"><tt class="docutils literal"><span class="pre">LogRead.currentOffset</span></tt>: return cookie representing current
read position (for use with <tt class="docutils literal"><span class="pre">LogRead.seek</span></tt>).</p>
</li>
<li><p class="first"><tt class="docutils literal"><span class="pre">LogRead.seek</span></tt>: set the read position to a value returned by
a prior call to <tt class="docutils literal"><span class="pre">LogWrite.currentOffset</span></tt> or <tt class="docutils literal"><span class="pre">LogRead.currentOffset</span></tt>,
or to the special <tt class="docutils literal"><span class="pre">SEEK_BEGINNING</span></tt> value. In a circular log, if
the specified position has been overwritten, behave as if
<tt class="docutils literal"><span class="pre">SEEK_BEGINNING</span></tt> was requested.</p>
<p><tt class="docutils literal"><span class="pre">SEEK_BEGINNING</span></tt> positions the read position at the beginning of
the oldest record still present in the log.</p>
<p>After reboot, the current read position is <tt class="docutils literal"><span class="pre">SEEK_BEGINNING</span></tt>.</p>
</li>
<li><p class="first"><tt class="docutils literal"><span class="pre">LogRead.getSize</span></tt>: return an approximation of the log's capacity
in bytes. Uses of <tt class="docutils literal"><span class="pre">sync</span></tt> and other overhead may reduce this number.</p>
</li>
</ul>
<p>For full details on arguments, etc, see the comments in the interface
definitions.</p>
<p>Note that while each call to <tt class="docutils literal"><span class="pre">append</span></tt> logically creates a separate
record, the <tt class="docutils literal"><span class="pre">LogStorageC</span></tt> API does not report record
boundaries. Additionally, crashes, reboots, and appends after
wrap-around in a circular log can cause the loss of multiple consecutive
records. Taken together, these restrictions mean that a <tt class="docutils literal"><span class="pre">LogStorageC</span></tt>
implementation MAY internally aggregate several consecutive appends into
a single record. However, the guarantee that only whole records are lost
is sufficient to ensure that applications do not to have worry about
incomplete or inconsistent log entries.</p>
</div>
<div class="section">
<h2><a id="small-objects" name="small-objects">4.4 Small objects:</a></h2>
<p>Sensor network applications need to store configuration data, e.g.,
mote identity, radio frequency, sample rates, etc. Such data is not large, but
losing it may lead to a mote misbehaving or losing contact with the
network.</p>
<p>The <tt class="docutils literal"><span class="pre">ConfigStorageC</span></tt> abstraction stores a single small object in a volume. It:</p>
<ul class="simple">
<li>Assumes that configuration data is relatively small (a few
hundred bytes).</li>
<li>Allows random reads and writes.</li>
<li>Has simple transactional behaviour: each read is a separate transaction,
all writes up to a commit form a single transaction.</li>
<li>At reboot, the volume contains the data as of the most recent successful
commit.</li>
</ul>
<p>Small objects are accessed by instantiating a ConfigStorageC component
which takes a volume id argument:</p>
<pre class="literal-block">
generic configuration ConfigStorageC(volume_id_t volid) {
  provides {
      interface Mount;
      interface ConfigStorage;
  }
} ...
</pre>
<p>A small object MUST be mounted (via the <tt class="docutils literal"><span class="pre">Mount</span></tt> interface) before
the first use.</p>
<p>The <tt class="docutils literal"><span class="pre">Mount</span></tt> and <tt class="docutils literal"><span class="pre">ConfigStorage</span></tt> interfaces (briefly presented in
Appendix B) contain the following operations (all split-phase except
<tt class="docutils literal"><span class="pre">ConfigStorage.getSize</span></tt> and <tt class="docutils literal"><span class="pre">ConfigStorage.valid</span></tt>):</p>
<ul class="simple">
<li><tt class="docutils literal"><span class="pre">Mount.mount</span></tt>: mount the volume.</li>
<li><tt class="docutils literal"><span class="pre">ConfigStorage.valid</span></tt>: return TRUE if the volume contains a
valid small object.</li>
<li><tt class="docutils literal"><span class="pre">ConfigStorage.read</span></tt>: read some bytes starting at a given offset.
Fails if the small object is not valid. Note that this reads the
data as of the last successful commit.</li>
<li><tt class="docutils literal"><span class="pre">ConfigStorage.write</span></tt>: write some bytes to a given offset.</li>
<li><tt class="docutils literal"><span class="pre">ConfigStorage.commit</span></tt>: make the small object contents reflect all the
writes since the last commit.</li>
<li><tt class="docutils literal"><span class="pre">ConfigStorage.getSize</span></tt>: return the number of bytes that can be stored
in the small object.</li>
</ul>
<p>For full details on arguments, etc, see the comments in the interface
definitions.</p>
</div>
</div>
<div class="section">
<h1><a id="implementations" name="implementations">5. Implementations</a></h1>
<p>An AT45DB implementation can be found in tinyos-2.x/tos/chips/at45db.</p>
<p>An ST M25P implementation can be found in tinyos-2.x/tos/chips/stm25p.</p>
</div>
<div class="section">
<h1><a id="authors-addresses" name="authors-addresses">6. Authors' Addresses</a></h1>
<div class="line-block">
<div class="line">David Gay</div>
<div class="line">2150 Shattuck Ave, Suite 1300</div>
<div class="line">Intel Research</div>
<div class="line">Berkeley, CA 94704</div>
<div class="line"><br /></div>
<div class="line">phone - +1 510 495 3055</div>
<div class="line">email - <a class="reference" href="mailto:david.e.gay&#64;intel.com">david.e.gay&#64;intel.com</a></div>
<div class="line"><br /></div>
<div class="line"><br /></div>
<div class="line">Jonathan Hui</div>
<div class="line">657 Mission St. Ste. 600</div>
<div class="line">Arched Rock Corporation</div>
<div class="line">San Francisco, CA 94105-4120</div>
<div class="line"><br /></div>
<div class="line">phone - +1 415 692 0828</div>
<div class="line">email - <a class="reference" href="mailto:jhui&#64;archedrock.com">jhui&#64;archedrock.com</a></div>
</div>
</div>
<div class="section">
<h1><a id="citations" name="citations">7. Citations</a></h1>
<table class="docutils footnote" frame="void" id="id5" rules="none">
<colgroup><col class="label" /><col /></colgroup>
<tbody valign="top">
<tr><td class="label"><a name="id5">[1]</a></td><td>David Gay. &quot;Design of Matchbox, the simple filing system for
motes. (version 1.0).&quot;</td></tr>
</tbody>
</table>
<table class="docutils footnote" frame="void" id="id6" rules="none">
<colgroup><col class="label" /><col /></colgroup>
<tbody valign="top">
<tr><td class="label"><a name="id6">[2]</a></td><td>TEP 2: Hardware Abstraction Architecture.</td></tr>
</tbody>
</table>
</div>
<div class="section">
<h1><a id="appendix-a-haa-for-some-existing-flash-chips" name="appendix-a-haa-for-some-existing-flash-chips">Appendix A. HAA for some existing flash chips</a></h1>
<div class="section">
<h2><a id="a-1-at45db" name="a-1-at45db">A.1 AT45DB</a></h2>
<p>The Atmel AT45DB family HPL is:</p>
<pre class="literal-block">
configuration HplAt45dbC {
  provides interface HplAt45db;
} ...
</pre>
<p>The <tt class="docutils literal"><span class="pre">HplAt45db</span></tt> interface has flash-&gt;buffer, buffer-&gt;flash, compare
buffer to flash, erase page, read, compute CRC, and write operations.  Most
of these operations are asynchronous, i.e., their completion is signaled
before the flash chip has completed the operation. The HPL also includes
operations to wait for asynchronous operations to complete.</p>
<p>A generic, system-independent implementation of the HPL
(<tt class="docutils literal"><span class="pre">HplAt45dbByteC</span></tt>) is included allowing platforms to just provide SPI and
chip selection interfaces.</p>
<p>Different members of the AT45DB family are supported by specifying a few
constants (number of pages, page size).</p>
<p>The AT45DB HAL has two components, one for chip access and the other
providing volume information:</p>
<pre class="literal-block">
component At45dbC
{
  provides {
    interface At45db;
    interface Resource[uint8_t client];
    interface ResourceController;
    interface ArbiterInfo;
  }
} ...

configuration At45dbStorageManagerC {
  provides interface At45dbVolume[volume_id_t volid];
} ...
</pre>
<p>Note that the AT45DB HAL resource management is independent of the
underlying HPL's power management. The motivation for this is that
individual flash operations may take a long time, so it may be desirable to
release the flash's bus during long-running operations.</p>
<p>The <tt class="docutils literal"><span class="pre">At45db</span></tt> interface abstracts from the low-level HPL operations by:</p>
<ul class="simple">
<li>using the flash's 2 RAM buffers as a cache to allow faster reads and
writes</li>
<li>hiding the asynchronous nature of the HPL operations</li>
<li>verifying that all writes were successful</li>
</ul>
<p>It provides cached read, write and CRC computation, and page erase and
copy. It also includes flush and sync operations to manage the cache.</p>
<p>The <tt class="docutils literal"><span class="pre">At45dbVolume</span></tt> interface has operations to report volume size and
map volume-relative pages to absolute pages.</p>
</div>
<div class="section">
<h2><a id="a-2-st-m25p" name="a-2-st-m25p">A.2 ST M25P</a></h2>
<p>The ST M25P family HPL is:</p>
<pre class="literal-block">
configuration Stm25pSpiC {
  provides interface Init;
  provides interface Resource;
  provides interface Stm25pSpi;
}
</pre>
<p>The <tt class="docutils literal"><span class="pre">Stm25pSpi</span></tt> interface has read, write, compute CRC, sector erase
and block erase operations. The implementation of this HPL is
system-independent, built over a few system-dependent components
providing SPI and chip selection interfaces.</p>
<p>Note that these two examples have different resource management policies:
the AT45DB encapsulates resource acquisition and release within each
operation, while the M25P family requires that HPL users acquire and
release the resource itself.</p>
<p>The ST M25P HAL is:</p>
<pre class="literal-block">
configuration Stm25pSectorC {
  provides interface Resource as ClientResource[storage_volume_t volume];
  provides interface Stm25pSector as Sector[storage_volume_t volume];
  provides interface Stm25pVolume as Volume[storage_volume_t volume];
}
</pre>
<p>The <tt class="docutils literal"><span class="pre">Stm25pSector</span></tt> interface provides volume-relative operations similar
to those from the HPL interface: read, write, compute CRC and
erase. Additionally, it has operations to report volume size and remap
volume-relative addresses. Clients of the ST M25P HAL must implement the
<tt class="docutils literal"><span class="pre">getVolumeId</span></tt> event of the <tt class="docutils literal"><span class="pre">Stm25pVolume</span></tt> interface so that the HAL can
obtain the volume id of each of its clients.</p>
</div>
</div>
<div class="section">
<h1><a id="appendix-b-storage-interfaces" name="appendix-b-storage-interfaces">Appendix B. Storage interfaces</a></h1>
<p>These interfaces are presented briefly here for reference; please refer
to the TinyOS documentation for a full description of the commands,
events and their parameters.</p>
<div class="section">
<h2><a id="b-1-blockstorage-interfaces" name="b-1-blockstorage-interfaces">B.1 BlockStorage interfaces</a></h2>
<p>The BlockStorage interfaces are:</p>
<pre class="literal-block">
interface BlockRead {
  command error_t read(storage_addr_t addr, void* buf, storage_len_t len);
  event void readDone(storage_addr_t addr, void* buf, storage_len_t len,
                      error_t error);

  command error_t computeCrc(storage_addr_t addr, storage_len_t len,
                             uint16_t crc);
  event void computeCrcDone(storage_addr_t addr, storage_len_t len,
                            uint16_t crc, error_t error);

  command storage_len_t getSize();
}

interface BlockWrite {
  command error_t write(storage_addr_t addr, void* buf, storage_len_t len);
  event void writeDone(storage_addr_t addr, void* buf, storage_len_t len,
                       error_t error);

  command error_t erase();
  event void eraseDone(error_t error);

  command error_t sync();
  event void syncDone(error_t error);
}
</pre>
</div>
<div class="section">
<h2><a id="b-2-configstorage-interfaces" name="b-2-configstorage-interfaces">B.2 ConfigStorage interfaces</a></h2>
<p>The ConfigStorage interfaces are:</p>
<pre class="literal-block">
interface Mount {
  command error_t mount();
  event void mountDone(error_t error);
}

interface ConfigStorage {
  command error_t read(storage_addr_t addr, void* buf, storage_len_t len);
  event void readDone(storage_addr_t addr, void* buf, storage_len_t len,
                      error_t error);

  command error_t write(storage_addr_t addr, void* buf, storage_len_t len);
  event void writeDone(storage_addr_t addr, void* buf, storage_len_t len,
                       error_t error);

  command error_t commit();
  event void commitDone(error_t error);

  command storage_len_t getSize();
  command bool valid();
}
</pre>
</div>
<div class="section">
<h2><a id="b-3-logstorage-interfaces" name="b-3-logstorage-interfaces">B.3 LogStorage interfaces</a></h2>
<p>The LogStorage interfaces are:</p>
<pre class="literal-block">
interface LogRead {
  command error_t read(void* buf, storage_len_t len);
  event void readDone(void* buf, storage_len_t len, error_t error);

  command storage_cookie_t currentOffset();

  command error_t seek(storage_cookie_t offset);
  event void seekDone(error_t error);

  command storage_len_t getSize();
}

interface LogWrite {
  command error_t append(void* buf, storage_len_t len);
  event void appendDone(void* buf, storage_len_t len, bool recordsLost,
                        error_t error);

  command storage_cookie_t currentOffset();

  command error_t erase();
  event void eraseDone(error_t error);

  command error_t sync();
  event void syncDone(error_t error);
}
</pre>
</div>
</div>
</div>
</body>
</html>
